Visual environment databases for simulating outdoor real-world type settings can be considered geographically large. This is in contrast to the small locally contained “theaters” which are employed in the CAD/CAM, entertainment and gaming industries. Visual environment databases that are geographically large employ a thorough level-of-detail (LOD) strategy to ensure that the important geographic features and objects near the instantaneous view position or eyepoint get displayed. This process of selecting what should be drawn at various levels of detail cannot be as simple as “on” or “off” decisions about what polygons or objects should be drawn. In order to make the computer generated scene appear realistic, the distant scene is still represented, but many of the scene elements that comprise the distant scene can use simpler versions of the scene element. Furthermore, to make the distant scene more believable, the distant scene can gradually transition into an acceptable nearby scene as the eyepoint approaches. Today's simulation users and customers want the simulated environment to be uniformly rich and dense everywhere, not just at a few places of interest.
The effectiveness of the visual scene can be considered to be directly proportional to the sophistication and thoroughness of the LOD strategy employed. Fewer levels-of-detail (LODs) and poorer transition mechanisms translate to a higher image generator (IG) load, lower apparent scene density, and distracting LOD transitions or anomalies. Some of the first large-area geo-specific databases that were used a few decades ago averaged about 3 polygons per square mile. During this early era, system designers began a rigorous application of a multiple-LOD methodology and by the mid-80's database density had risen to roughly 7,000 polygons per square mile. These databases can also be geographically large. For example, a database of just the west coast of the United States can be over 250,000 square miles.
The product of database geographic density and database geographic extent yields a “virtual content” or a number of stored polygons in the database that can be astronomical. For example, 7,000 polygons/sq-mi×250,000 sq-mi yields a “virtual content” of nearly 2×109 polygons. In other words, the database may contain billions of polygons. This total number of polygons that could possibly be viewed is generally pared down to roughly 10,000 run-time polygons for processing by the image generator (IG). The particular 10,000 polygons that are selected for rendering and viewing are always changing as the eyepoint moves. The selection process can be thought of as a funnel with a very large mouth into which the entire database is dumped for each frame of output (e.g., 60 times a second). The IG sits at the tiny outlet of the funnel and renders the 10,000 or so polygons the IG is capable of handling. A mechanism within the funnel can decide based on the instantaneous position of the eyepoint which of the 2×109 input polygons to pare down to the 10,000 polygons for the IG.
This selection, culling and management mechanism is the database scene graph. The scene graph performs a range-driven hierarchical geographic subdivision of the entire database. The subdivision hierarchy is basically the LOD decision tree. Geographic areas distant from the instantaneous eyepoint are subdivided less and culled out in larger pieces. Areas near the instantaneous eyepoint are subdivided more and culled more finely. Each decision point or node of the graph allows the selection of either simpler or more complex “filler” (e.g., polygons and objects) for the geographic area represented, based on range from the eyepoint. At each node of the graph, the system basically decides whether the accompanying displayable elements are adequate for the current range, or whether further subdivision and selection is necessary. The processes just described are applied to the terrain as well as the features decorating the terrain.
When considering LOD, it is very undesirable to render the terrain at a single, fixed level of detail. For example, current system users and customers desire to have terrain detail near the eyepoint that is equivalent to a general minimum of 100 meter terrain facets. This translates to about 500 polygons per square mile. If the system visibility range is 200 miles which is not atypical, then the terrain skin alone can present about 10 million terrain triangles for a single visual processing channel. With a level-of-detail (LOD) terrain strategy that is set to a single level, a 5,000 polygon per channel terrain budget would imply 2 mile terrain facets. Unfortunately, the world is pretty bland when sampled this coarsely. Accordingly, the terrain skin itself is more effective with a range-driven hierarchical level of detail.
Using a range-driven LOD for the terrain creates problems because the non-terrain scene features are geometrically attached to the terrain. This means that the non-terrain scene features (e.g., buildings, roads, etc.) are incorporated into the scene graph and controlled by the terrain LOD strategy. The terrain LOD strategy thus becomes the single controlling mechanism to which all other feature behavior is subordinate. Accordingly, every scene feature is merged into the scene graph at the terrain node that contains it, and at a terrain LOD for a range consistent with the desired LOD behavior of the feature. In general, this means that the feature can spring into visual existence only after its underlying terrain has reached the highest LOD. When this distracting behavior is observable by an end user, this instant appearance of a feature is sometimes known as feature “pop-up”.
If a feature is desired to exist at more distant ranges, the feature must be simultaneously attached to the graph at two or more terrain nodes (or one node for each LOD). This complicates the LOD evolution of the underlying terrain. Attaching features at multiple terrain nodes also creates the problem of what the feature should do while the graph is executing a fade between branches, and the fade is applied hierarchically to everything further down on both branches.
One practical effect of these difficulties is that the simulation modelers may design the terrain to arrive at its highest LOD too far away, which wastes IG capacity. On the other hand, delaying some feature introduction until the features are too close can cause visual distraction. Furthermore, simulation modelers are naturally, but reluctantly, led to avoid terrain strategies with small final facets because these small facets would normally work best with fairly close transition ranges. There are also particular problems with the application of scene features that necessarily straddle multiple terrain facets (roads, etc.), and those features such as point lights that must be introduced into the scene at long range, yet remain attached to the terrain. As a result, a number of capabilities increasingly demanded by end users and customers have simply not been possible or implementing certain features has been intractably difficult. In the meantime, database sizes have grown to terabytes and compilation times have grown to CPU months. Notwithstanding this, the geographic density remains at 1985 levels.
Geographic density has not been able to increase because there is a single database graph, and the database syntax (“schema”) must be rich enough to accomplish the control functions for all the types of scene features that may be incorporated into the database. Two consequences of this are that the graph walk itself is more complex and compute-intensive than it would otherwise be, and changes to the schema require a full database rebuild. In addition, since the graph is significantly affected by the selected terrain LOD strategy and geometry, any changes to the terrain require a complete database rebuild or recompile. The graph provides the range-based LOD decision mechanism, and this mechanism is “global” in that LOD decisions apply hierarchically to all subordinate scene elements. Thus, there is basically one LOD control or “throttle” which can manage the image generator (IG) overload, and all the scene features respond to the LOD control uniformly. Having only one LOD retains or discards features in a way that is not necessarily gradual when there is an impending processing overload. Further, the iterative process of matching the database load to the IG capacity involves wholesale database rebuilds with little fine-tuning control.
Scene features are assigned to nodes in the graph based on their geographic position. These relationships are fixed at database compile time. Thus lateral betweening or lateral movement of features is generally prohibited at run time. Regrettably, lateral betweening is particularly suited to the LOD simplification of vector-based features. In fact, any run-time lateral adjustment of any feature may cause a visual conflict, so even simple or otherwise solvable adjustments are disallowed. Features that involve complex interaction with the terrain (e.g., road cuts and fills) are entirely clipped and placed (or “solved”) at compile time, and the appropriate controls are frequently embedded into feature vertices to allow run-time vertical betweening of the terrain. This makes run-time modification of the terrain problematic. Users of ground warfare simulations want to conduct long simulations that involve terrain-modifying processes. Examples of events that may modify the terrain are bomb craters, bulldozers, creating berms, etc. Unfortunately, existing features that are already clipped, conformed and linked to the terrain in the graph are not typically able to respond to these dynamic changes.
The clipping and conforming processes generate additional compile-time geometry that must be stored and later retrieved. This additional geometry is partly responsible for the huge increase in stored database size. These complexities also become part of the schema problem. In the end, the modeling tools being used increase in complexity and interdependence, resulting in an integrated but unwieldy suite of tools that is expensive, difficult to maintain, complicated to extend, and resource-hungry.
The debug of such databases is also complicated by the all or nothing nature of the single, compiled database graph. If there is a major error in the database graph, the system might not display any image at all, and the visual anomalies connected with graph errors may not be intuitively connected to the source of the error.